package fpt.myFileHandler;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

import fpt.graph.*;


/**
 * Functions
 * 
 * r41
 * 
 * 12 March 2010
 * 
 * This file is to contain all the common functions and procedures used in this project.
 * @author Daniel De Guzman
 *
 */
public class Functions {
	
	/**
	 * Gets string from specified index value of processedInput and
	 * turns it into an integer.
	 * @param lineNumber - index value of string array
	 * @return Integer value of string found in specified index
	 */
	public static int getValue(String[] input, int lineNumber){
		if (input[lineNumber].equals(""))
			return 0;
		else
			return Integer.parseInt(input[lineNumber]);
	}
	
	/**
	 * Checks each vertex information format using Regular expressions.
	 * Each vertex must follow the following pattern: "\w+, [ \w]+"
	 * @return true - if vertex information is valid
	 */
	public static Boolean checkVertexInfo(String[] vertexInfo){
		Pattern pattern = Pattern.compile("\\w+,[ \\w]+");
		Matcher matcher;
		int len = vertexInfo.length;
		Boolean[] lineBool = new Boolean[len];
		for (int i = 0; i < len; i++){
			lineBool[i] = false;
			matcher = pattern.matcher(vertexInfo[i]);
			while (matcher.find()){
				lineBool[i] = true;
			} 
		}
		return processBooleanArray(lineBool);
	}
	
	/**
	 * Processes a list of booleans.
	 * @param boolist - List of booleans
	 * @return true - if all elements are true
	 */
	public static Boolean processBooleanArray(Boolean[] boolist){
		Boolean result = true;
		int i = 0;
		while (result && (i != boolist.length)){
			if (!boolist[i])
				result = false;
			i++;
		}
		return result;
	}
	
	/**
	 * Checks the processed input's format. The file must have:
	 * <ol>
	 * 	<li>Parameter K, an integer, on the first line,</li>
	 * 	<li>Vertex Count, an integer, on the second line,</li>
	 * 	<li>List of vertices and their neighbours. For each line:</li>
	 *		<ul>
	 *		<li>A label for the vertex, followed by a comma and a space.</li>
	 *		<li>A list of labels of vertices that are adjacent to the
	 *			current vertex, each followed by a space.</li>
	 *		</ul>
	 * </ol>
	 * @param k - Parameter k
	 * @param vCount - Vertex Count
	 * @param vInfo - Vertex Information
	 * @param error - Error Message, if any
	 * @return true if all requirements are met
	 */
	public static Boolean processFile(Handler h){
		if (h.getK() != 0){
			if (h.getvCount() != 0){
				if (h.getvCount() == (h.getvInfoArray().length)){
					if (checkVertexInfo(h.getvInfoArray())){
						return true;
					} 
					else {
						h.setError(Messages.errorVInfo);
						return false;
					}
				} else {
					h.setError(Messages.errorVCCompare);
					return false;
				}
			} else {
				h.setError(Messages.errorVC);
				return false;
			}
		} else {
			h.setError(Messages.errorK);
			return false;
		}
	}
	
	/**
	 * Implements the kernelization phase on the input graph. Kernelization's
	 * three rules are as follows:
	 * <ol>
	 * 	<li>Firstly, remove isolated vertices from the graph.</li>
	 * 	<li>Secondly:
	 * 		<ul>
	 * 			<li>Remove vertices of degree 1 from the graph.</li>
	 * 			<li>Add its neighbour to the vertex cover</li>
	 * 			<li>Decrement k</li>
	 *		</ul>
	 *  </li>
	 *  <li>Lastly:
	 *  	<ul>
	 *  		<li>Add vertices greater than k to the vertex cover</li>
	 *  		<li>Remove this vertex from the graph</li>
	 *  		<li>Decrement k</li>
	 *  	</ul>
	 *  </li>
	 * </ol>
	 * These rules are applied recursively, until k is zero or kernelization
	 * cannot be applied any longer.
	 * @param graphInfo - input graph
	 * @return Undirected graph after applying kernelization
	 */
	public static GraphFPT kernelize(GraphFPT graphInfo){
		int k = graphInfo.getK();
		List<String> vertexCover = graphInfo.getVertexCover();
		HashMap<String, String[]> graph = graphInfo.getGraph();
		HashMap<String, String> removed = new HashMap<String, String>();
		
		boolean mod = true;		// value to check if the graph has been modified or not
		
		while (mod != false && k >= 0){
			mod = false;
			String[] vertices = graph.keySet().toArray(new String[graph.keySet().size()]);
			
			int vertLen = vertices.length;
			for (int counter = 0; counter < vertLen; counter++){
				String current = vertices[counter];
				String[] neighbours = graph.get(current);
				
				if (neighbours == null){
					// Do nothing if the current neighbour is null
				} else
					
				// Rule 1
				if (neighbours.length == 0){
					removed.put(current, Messages.kzRuleOne);
					graph.remove(current);
					mod = true;
				} else
					
				// Rule 2
				if (neighbours.length == 1){
					String neighbour = neighbours[0];
					removed.put(current, Messages.kzRuleTwo);
					if (!vertexCover.contains(neighbour)){
						removed.put(neighbour, Messages.kzCovAdd);
						vertexCover.add(neighbour);
						k--;
						
						// Find each occurrence of the vertex that was added into the cover
						// and remove it from each of its neighbours
						String[] vCovnb = graph.get(neighbour);
						for (String s: vCovnb){
							String[] snb = graph.get(s);
							List<String> newSnb= new ArrayList<String>();
							for (String t: snb){
								if (!t.equals(neighbour)){
									newSnb.add(t);
								}
							}
							graph.put(s, newSnb.toArray(new String[newSnb.size()]));
						}
						graph.remove(neighbour);
					}
					graph.remove(current);
					mod = true;
				} else
					
				// Rule 3
				if (neighbours.length > k){
					if (!vertexCover.contains(current)){
						removed.put(current, Messages.kzRuleThree);
						vertexCover.add(current);
						k--;
						String[] vCovnb = graph.get(current);
						for (String s: vCovnb){
							String[] snb = graph.get(s);
							List<String> newSnb= new ArrayList<String>();
							for (String t: snb){
								if (!t.equals(current)){
									newSnb.add(t);
								}
							}
							graph.put(s, newSnb.toArray(new String[newSnb.size()]));
						}
						graph.remove(current);
					}
					mod = true;
				}
			}
		}

		GraphFPT output = new GraphFPT(k, graph, vertexCover, removed);
		
		return output;
	}
	
	/**
	 * Implements the depth-bound search tree algorithm provided in the 
	 * notes. The rules it follows are:
	 * <ol>
	 * 	<li>If there is a degree 1 vertex, its neighbour is added to the 
	 * 		vertex cover</li>
	 * 	<li>If there is a degree 2 vertex, then either
	 * 		<ul>
	 * 			<li>Both neighbours are added into the vertex cover, or
	 * 			</li>
	 * 			<li>The vertex and its neighbour's neighbours are added 
	 * 				into the vertex cover</li>  
	 * 		</ul>
	 * 	</li>
	 * 	<li>If there is a degree 3 vertex, then either
	 * 		<ul>
	 * 			<li>the vertex is added into the vertex cover, or </li>
	 * 			<li>Its neighbour's neighbours are added into the vertex
	 * 				cover</li>  
	 * 		</ul>
	 * 	</li>
	 * 	</li>
	 * </ol>
	 * @param currentNode
	 */
	public static void boundedSearch(SearchTreeNode currentNode){
		int k = currentNode.getK();
		HashMap<String, String[]> graph = currentNode.getGraph();
		HashMap<String, String> removed = currentNode.getRemoved();
		List<String> vertexCover = currentNode.getVertexCover();
		
		// Kernelize again and set new variables
		GraphFPT temp = kernelize(new GraphFPT(k, graph, vertexCover, removed));
		currentNode.setK(temp.getK());
		currentNode.setGraph(temp.getGraph());
		currentNode.setVertexCover(temp.getVertexCover());
		currentNode.setRemoved(temp.getRemoved());
		
		int counter = 0;
		String[] vertices = graph.keySet().toArray(new String[graph.keySet().size()]);
		int verticesLen = vertices.length;
		if (verticesLen > 0 && k > 0) {
			String currentVertex = vertices[counter];
			String[] neighbours = graph.get(currentVertex);	
			int nbLength = neighbours.length;
			
			// Find suitable graph entries
			while (nbLength > 3){
				counter++;
				currentVertex = vertices[counter];
				neighbours = graph.get(currentVertex);
				nbLength = neighbours.length;
			} 
			
			// Rule 1: Add neighbour to cover
			if (nbLength == 1){	
				// Create child for current node
				SearchTreeNode singleChild = duplicateNode(currentNode);
				int k1 = singleChild.getK();
				singleChild.setName(Messages.bstFirstChildName(currentNode.getName()));
				List<String> cover1 = singleChild.getVertexCover();
				HashMap<String, String> rem1 = singleChild.getRemoved();
				HashMap<String, String[]> g1 = singleChild.getGraph();
				
				// Add neighbour to cover
				String neighbour = neighbours[0];
				if (!cover1.contains(neighbour)){
					rem1.put(neighbour, Messages.bstCovAdd);
					cover1.add(neighbour);
					k1--;
					singleChild.setK(k1);
					
					// Find each occurrence of the neighbour in the remaining graph
					String[] vCovnb = g1.get(neighbour);
					for (String s: vCovnb){
						String[] snb = g1.get(s);
						List<String> newSnb= new ArrayList<String>();
						for (String t: snb){
							if (!t.equals(neighbour)){
								newSnb.add(t);
							}
						}
						g1.put(s, newSnb.toArray(new String[newSnb.size()]));
					}
					g1.remove(neighbour);
				}
				g1.remove(currentVertex);
				
				// Set as current node's first child and use algorithm on the child
				currentNode.setFirstChild(singleChild);
				boundedSearch(singleChild);
			} else
			
			// Rule 2: Either
			//			> Add both neighbours to cover
			//			> Add currentVertex and its neighbours' neighbours to cover
			if (nbLength == 2){
				// Create Children
				
				// Create First Child 
				//	> Add both neighbours to cover
				SearchTreeNode firstChild = duplicateNode(currentNode);
				int k1 = firstChild.getK();
				firstChild.setName(Messages.bstFirstChildName(currentNode.getName()));
				List<String> fcCover = firstChild.getVertexCover();
				HashMap<String, String> rem1 = firstChild.getRemoved();
				HashMap<String, String[]> g1 = firstChild.getGraph();
				
				// Find each occurrence of the current vertex and remove from the graph
				String[] neighbours1 = g1.get(currentVertex);
				for (String neighbour : neighbours1){
					if (!fcCover.contains(neighbour)){
						rem1.put(neighbour, Messages.bstCovAdd);
						fcCover.add(neighbour);
						k1--;
						firstChild.setK(k1);
						
						String[] remove = g1.get(neighbour);
						for (String s: remove){
							String[] snb = g1.get(s);
							List<String> newSnb= new ArrayList<String>();
							for (String t: snb){
								if (!t.equals(neighbour)){
									newSnb.add(t);
								}
							}
							g1.put(s, newSnb.toArray(new String[newSnb.size()]));
						}
						g1.remove(neighbour);
					}
				}
				g1.remove(currentVertex);
				
				// Set as current node's first child and redo search algorithm
				currentNode.setFirstChild(firstChild);
				boundedSearch(firstChild);
				
				// Create Second Child
				//	> Current Vertex and its neighbours' neighbours are in the cover
				SearchTreeNode secondChild = duplicateNode(currentNode);
				int k2 = secondChild.getK();
				secondChild.setName(Messages.bstSecondChildName(currentNode.getName()));
				List<String> scCover = secondChild.getVertexCover();
				HashMap<String, String> rem2 = secondChild.getRemoved();
				HashMap<String, String[]> g2 = secondChild.getGraph();
				
				// Add current vertex to cover
				String[] neighbours2 = g2.get(currentVertex);
				if (!scCover.contains(currentVertex)){
					rem2.put(currentVertex, Messages.bstCovAdd);
					scCover.add(currentVertex);
					k2--;
					secondChild.setK(k2);
					
					// Go through neighbours and remove all occurrences from graph
					for (String s: neighbours2){
						String[] snb = g2.get(s);
						List<String> newSnb= new ArrayList<String>();
						for (String t: snb){
							if (!t.equals(currentVertex)){
								newSnb.add(t);
							}
						}
						g2.put(s, newSnb.toArray(new String[newSnb.size()]));
					}
				}
				
				// Add neighbour's neighbours to cover
				for (String neighbour : neighbours2){
					// neighbour's neighbours
					String[] nbsNBS = g2.get(neighbour);
					for (String nbs : nbsNBS){
						if (!scCover.contains(nbs)){
							rem2.put(nbs, Messages.bstCovAdd);
							scCover.add(nbs);
							k2--;
							secondChild.setK(k2);
							
							// neighbour's neighbour's neighbours
							String[] n = g2.get(nbs);
							for (String s : n){
								String[] snb = g2.get(s);
								List<String> newSnb= new ArrayList<String>();
								for (String t: snb){
									if (!t.equals(nbs)){
										newSnb.add(t);
									}
								}
								g2.put(s, newSnb.toArray(new String[newSnb.size()]));
							}
							g2.remove(nbs);
						}
					}
					g2.remove(neighbour);
				}
				g2.remove(currentVertex);
				
				// Set as second child and redo algorithm
				currentNode.setSecondChild(secondChild);
				boundedSearch(secondChild);
				
			} else
				
			// Rule 3: Either
			//			> currentVertex is in the cover
			//			> all of its neighbours are in the cover
			if (nbLength == 3){
				// Create Children
				
				// Create First Child
				//	> Current vertex is in the cover
				SearchTreeNode firstChild = duplicateNode(currentNode);				
				int k1 = firstChild.getK();
				String name1 = currentNode.getName() + "'s First Child";
				firstChild.setName(name1);
				List<String> fcCover = firstChild.getVertexCover();
				HashMap<String, String> rem1 = firstChild.getRemoved();
				HashMap<String, String[]> g1 = firstChild.getGraph();
				
				// Add vertex to cover
				if (!fcCover.contains(currentVertex)){
					rem1.put(currentVertex, Messages.bstRuleThree1);
					fcCover.add(currentVertex);
					k1--;
					firstChild.setK(k1);
					
					// Go through neighbours and remove all occurrences from graph
					String[] neighbours1 = g1.get(currentVertex);
					for (String s: neighbours1){
						String[] snb = g1.get(s);
						List<String> newSnb= new ArrayList<String>();
						for (String t: snb){
							if (!t.equals(currentVertex)){
								newSnb.add(t);
							}
						}
						g1.put(s, newSnb.toArray(new String[newSnb.size()]));
					}
					g1.remove(currentVertex);
					
					// Set first child as current node's first child and go through algorithm again 
					currentNode.setFirstChild(firstChild);
					boundedSearch(firstChild);
				}
				
				// Create Second Child
				//	> Add neighbours to cover
				SearchTreeNode secondChild = duplicateNode(currentNode);
				int k2 = secondChild.getK();
				String name2 = currentNode.getName() + "'s Second Child";
				secondChild.setName(name2);
				List<String> scCover = secondChild.getVertexCover();
				HashMap<String, String> rem2 = secondChild.getRemoved();
				HashMap<String, String[]> g2 = secondChild.getGraph();
				
				// for each neighbour, add to cover and remove from graph
				String[] neighbours2 = g2.get(currentVertex);
				for (String neighbour : neighbours2){
					if (!scCover.contains(neighbour)){
						rem2.put(neighbour, Messages.bstRuleThree2);
						scCover.add(neighbour);
						k2--;
						
						secondChild.setK(k2);
						
						// Neighbour's neighbours
						String[] nbsNB = g2.get(neighbour);
						for (String s : nbsNB){
							String[] NB = g2.get(s);
							List<String> newNB = new ArrayList<String>();
							for (String t : NB){
								if (!t.equals(neighbour)){
									newNB.add(t);
								}
							}
							g2.put(s, newNB.toArray(new String[newNB.size()]));
						}
						g2.remove(neighbour);		
					}
				}
				g2.remove(currentVertex);
				
				// Set as current node's second child and redo search
				currentNode.setSecondChild(secondChild);
				boundedSearch(secondChild);
			}
		}
	}
	
	/**
	 * Creates a copy of a search tree node
	 * @param node - a SearchTreeNode
	 * @return SearchTreeNode - the exact duplicate
	 */
	private static SearchTreeNode duplicateNode(SearchTreeNode node){
		// Get source data
		int srcK = node.getK();
		String srcName = node.getName();
		List<String> srcCover = node.getVertexCover();
		HashMap<String, String> srcRem = node.getRemoved();
		HashMap<String, String[]> srcGraph = node.getGraph();
		
		// Output k, name and vertex cover
		String dstName = srcName;
		int dstK = srcK;
		List<String> dstCover = new ArrayList<String>();
		if (!srcCover.isEmpty()){
			for (String vertex: srcCover){
				dstCover.add(vertex);
			}
		}
		
		// output removed
		HashMap<String, String> dstRem = new HashMap<String, String>();
		if (!srcRem.isEmpty()){
			Iterator<?> iterator = srcRem.entrySet().iterator(); 
			while (iterator.hasNext()){
				Map.Entry entry = (Map.Entry) iterator.next();
				String vertex = (String) entry.getKey();
				String reason = (String) entry.getValue();
				dstRem.put(vertex, reason);
			}
		}
		
		// output graph
		HashMap<String, String[]> dstGraph = new HashMap<String, String[]>();
		if (!srcGraph.isEmpty()){
			String[] vertices = srcGraph.keySet().toArray(new String[srcGraph.keySet().size()]);
			for (String vertex : vertices){
				String[] neighbours = srcGraph.get(vertex);
				dstGraph.put(vertex, neighbours);
			}
		}
		// variables to create an output
		GraphFPT graphInfo = new GraphFPT(dstK, dstGraph, dstCover, dstRem);
		SearchTreeNode outNode = new SearchTreeNode(dstName, graphInfo);
		return outNode;
	}
	
	// Debugging functions
	
	/**
	 * Transforms a string array into one string
	 * @param sArray - string array
	 * @return a string
	 */
	private static String sArrayToString(String[] sArray){
		String out = "";
		for (int i = 0; i < sArray.length; i++)
			out += "  # "+ i + ". " + sArray[i] + Messages.newline;
		return out;
	}
	
	/**
	 * Output string to display debugging messages
	 * @return output string 
	 */
	private static String displayGraph(String message, HashMap<String, String[]> graph){
		String output = "";
		output += message + Messages.newline;
		Iterator<?> iterator = graph.entrySet().iterator();
		while (iterator.hasNext()){
			Map.Entry entry = (Map.Entry) iterator.next(); 
			String vertex = (String) entry.getKey();
			String[] neighbours = (String[]) entry.getValue();
			output += "Vertex " + vertex + " has " + neighbours.length  + " neighbours";
			if (neighbours.length == 0){
				output += "." + Messages.newline;
			} else 
			if (neighbours.length == 1){
				output += ", which is " + neighbours[0] + "." + Messages.newline;
			} else {
				output += ", which are ";
				for (int i = 0; i < neighbours.length; i ++){
					if (i == (neighbours.length-1)){
						output += "and " +neighbours[i] + "." + Messages.newline;
					} else {
						output += neighbours[i] + ", ";
					}
				}
			}
		}
		return output;
	}
	
	/**
	 * Display vertex cover contents for debugging
	 * @param vertexCover a List<String containing the vertex cover
	 * @return a string output if there is a vertex cover
	 */
	private static String displayVertexCover(List<String> vertexCover){
		String output = "";
		if  (!vertexCover.isEmpty()){
			output += vertexCover.size() + Messages.newline;
			for (String v: vertexCover){
				output += v + " ";
			}
			output += Messages.newline;
		}
		return output;
	}
	
	/**
	 * Display the contents of the removed vertices HashMap
	 * @param removed - a HashMap containing the removed vertices and the reason
	 * @return a string output of the HashMap if any
	 */
	private static String displayRemovedVertices(HashMap<String, String> removed){
		String output = "";
		if (!removed.isEmpty()){
			output += Messages.newline;
			output += "   Vertex   |              Reason " +  Messages.newline;
			Iterator<?> iterator = removed.entrySet().iterator();
			while (iterator.hasNext()){
				Map.Entry entry = (Map.Entry) iterator.next();
				String vertex = (String) entry.getKey();
				String reason = (String) entry.getValue();
				output += "      " + vertex + "     |   " + reason; 
			}
			output += Messages.newline;
		}
		return output;
	}
	
	/**
	 * Outputs a string for debugging purposes.
	 * @param handler - Any File Handler, such as RTFHandler or TXTHandler
	 * @return output string
	 */
	public static String debuggingFileProcessing(Handler handler){
		String output = "";
		output += Messages.thinBorder;
		output += Messages.fpProcInput;
		output += sArrayToString(handler.getProcessedInput());
		output += Messages.displayK(handler.getK());
		output += Messages.displayVC(handler.getvCount());
		output += Messages.displayActualVC(handler.getvInfoArray().length);
		output += Messages.fpVInfo;
		output += sArrayToString(handler.getvInfoArray());
		output += Messages.thinBorder;
		return output;
	}

	/**
	 * Outputs a string to debug graph creation
	 * @param graphInfo (GraphFPT)
	 * @return Output string
	 */
	public static String debuggingCreateGraph(String message, GraphFPT graphInfo) {
		String output = "";
		output += Messages.newline;
		output += Messages.thinBorder;
		output += Messages.gcHeader;
		output += Messages.displayK(graphInfo.getK());
		output += Messages.displayVC(graphInfo.getGraph().size());
		output += displayGraph(message, graphInfo.getGraph());
		output += displayVertexCover(graphInfo.getVertexCover());
		output += displayRemovedVertices(graphInfo.getRemoved());
		output += Messages.thinBorder;
		return output;
	}

	/**
	 * Displays node information for debugging and output purposes
	 * @param rootNode - SearchTreeNode node containing graph information
	 * @return an output string for debugging purposes
	 */
	public static String debuggingBoundedSearchTree(SearchTreeNode rootNode){
		String output = "";
		//output += Messages.newline;
		//output += Messages.thinBorder;
		//output += Messages.bstHeader;
		
		// Get node info
		int counter = 0;
		//output += Messages.displayTier(counter) + rootNode.getName() + Messages.newline;
		//output += Messages.displayK(rootNode.getK());
		if (rootNode.getK() < 0){
			output += "NO" + Messages.newline;
		} else {
			//output += displayVertexCover(rootNode.getVertexCover());
			//output += displayGraph("", rootNode.getGraph());
			//output += displayRemovedVertices(rootNode.getRemoved());
			//output += Messages.thinBorder;
			output += displayChildren(counter, rootNode);
			//output += Messages.border;
		}
		return output;
	}
	
	/**
	 * Displays parent node's children. Called recursively until children
	 * are null values
	 * @param counter - keeps count of tiers
	 * @param parent - parent node
	 * @return an output string for debugging
	 */
	private static String displayChildren(int counter, SearchTreeNode parent){
		String output = "";
		SearchTreeNode firstChild = parent.getFirstChild();
		SearchTreeNode secondChild = parent.getSecondChild();
		//output += Messages.thinBorder;
		if (firstChild == null){
			//output += Messages.displayTier(counter) + parent.getName() + "'s first child is null." + Messages.newline;
		} else {
			counter++;
			//output += Messages.displayTier(counter) + firstChild.getName() + Messages.newline;
			//output += Messages.displayK(firstChild.getK());	
			if (firstChild.getK() == 0 && firstChild.getGraph().isEmpty()) {
				//output += "FOUND: " + Messages.newline;
				output += displayVertexCover(firstChild.getVertexCover());
			} else if (firstChild.getK() < 0){
				output += "NO" + Messages.newline;
				//output += displayVertexCover(firstChild.getVertexCover());
			}
			
			//output += Messages.newline;
			//output += displayGraph("",firstChild.getGraph());
			output += displayChildren(counter, firstChild);
			counter--;
		}
		
		//output += Messages.thinBorder;
		if (secondChild == null){
			//output += Messages.displayTier(counter) + parent.getName() + "'s second child is null." + Messages.newline;
		} else {
			counter++;
			//output += Messages.displayTier(counter) + secondChild.getName() + Messages.newline;
			//output += Messages.displayK(secondChild.getK());
			if (secondChild.getK() == 0 && secondChild.getGraph().isEmpty()) {
				//output += "FOUND: " + Messages.newline;
				output += displayVertexCover(secondChild.getVertexCover());
			} else if (secondChild.getK() < 0){
				output += "NO" + Messages.newline;
				//output += displayVertexCover(secondChild.getVertexCover());
				
			}
			//output += Messages.newline;
			//output += displayGraph("",secondChild.getGraph());			
			output += displayChildren(counter, secondChild);
			counter--;
		}
		return output;
	}
}
